0% completed
Problem Statement
Given the two root nodes root1 and root2 of two different binary trees, return true if both binary trees are leaf-similar trees. Otherwise, return false.
All leaves of the binary tree in left-to-right order create a leaf sequence. If both trees have same leaf sequence, they are considered as leaf-similar tree.
Examples
Example 1:
- Input: root1 = [5,2,7,1,3,6,8], root2 = [7,5,2,1,3,6,8]
- Expected Output:
True - Justification: Both trees have the same leaf sequence [1,3,6,8], making them leaf-similar despite their different structures.
Example 2:
- Input: root1 = [7, null, 8], root2 = [7,8]
- Expected Output:
True - Justification: Both Tree A and Tree B have the same leaf sequence [8], making them leaf-similar.
Example 3:
- Input: root1 = [1,2,4,null,null,5,6], root2 = [1,2,5,null,null,4,6]
- Expected Output:
False - Justification: The leaf sequence for Tree A is [2,5,6], while for Tree B, it is [2,4,6]. Since the sequences do not match in order, the trees are not considered leaf-similar.
Solution
To solve this problem, we'll traverse each tree to extract the sequence of leaf nodes. The traversal approach ensures we accurately capture the order of leaves as they appear from left to right. By comparing these sequences directly, we can determine if the trees are leaf-similar. This method is effective because it isolates the aspect of the trees that matters for this problem—the leaf nodes—and disregards other structural differences. It's also efficient, as it focuses solely on leaf nodes and avoids unnecessary comparisons of non-leaf nodes.
Initially, we'll perform a depth-first search (DFS) on both trees. This search is ideal for navigating through each branch to its end, directly leading us to the leaves. By storing the leaf values in sequences (arrays or lists), we can easily compare these sequences once the traversals are complete. If the sequences are identical in both value and order, we conclude the trees are leaf-similar. This approach is straightforward yet powerful, leveraging the simplicity of DFS to address the core of what defines leaf similarity.
Step-by-Step Algorithm
-
Initialize Two Lists: Start by creating two empty lists,
leaves1andleaves2, which will store the sequences of leaf nodes for the first and second tree, respectively. -
Depth-First Search (DFS) Traversal:
- Implement a recursive function
dfs()that traverses the tree in a depth-first manner. - The function should take a
TreeNode(representing the current node in the traversal) and a list of integers (to store leaf values) as parameters.
- Implement a recursive function
-
Identify Leaf Nodes:
- In the
dfsfunction, check if the current node is a leaf node. A node is considered a leaf if it has no left or right child. - If the current node is a leaf, add its value to the
leaveslist passed as an argument.
- In the
-
Recursive DFS Calls:
- If the current node is not a leaf, recursively call the
dfsfunction on its left child (if it exists) and its right child (if it exists). - This step ensures that every node in the tree is visited, and all leaf nodes are identified and added to the
leaveslist.
- If the current node is not a leaf, recursively call the
-
Compare Leaf Sequences:
- After performing DFS traversals on both trees and obtaining their leaf sequences, compare these sequences for equality.
- The trees are considered "leaf-similar" if their leaf sequences are identical in both value and order. Return
trueif they are identical, orfalseotherwise.
Algorithm Walkthrough
Input Trees:
root1 = [5,2,7,1,3,6,8]
root2 = [7,5,2,1,3,6,8]
Step 1: Initialize two lists, leaves1 and leaves2, to hold the leaf sequences of root1 and root2, respectively.
Step 2: Perform a DFS traversal on root1.
- Start from the root node (5). It's not a leaf, so proceed to its children.
- Visit node 2. It's not a leaf, so proceed to its children.
- Visit node 1. It's a leaf, so add
1toleaves1. - Backtrack and visit node 3. It's a leaf, so add
3toleaves1.
- Visit node 1. It's a leaf, so add
- Backtrack to root and visit node 7. It's not a leaf, so proceed to its children.
- Visit node 6. It's a leaf, so add
6toleaves1. - Visit node 8. It's a leaf, so add
8toleaves1.
- Visit node 6. It's a leaf, so add
- After the traversal,
leaves1 = [1,3,6,8].
Step 3: Perform a DFS traversal on root2.
- Start from the root node (7). It's not a leaf, so proceed to its children.
- Visit node 5. It's not a leaf (considering the corrected structure to match the leaf sequence), so proceed to its children.
- Visit node 2. Proceed to its children.
- Visit node 1. It's a leaf, so add
1toleaves2. - Visit node 3. It's a leaf, so add
3toleaves2.
- Visit node 1. It's a leaf, so add
- Node 5 also leads to nodes 6 and 8 (right subtree of root or left subtree of node 7), where both are leaves, so add
6and8toleaves2.
- Visit node 2. Proceed to its children.
- After the traversal,
leaves2 = [1,3,6,8].
Step 4: Compare leaves1 and leaves2. Since they are identical ([1,3,6,8]), return true.
Code
Complexity Analysis
Time Complexity
- DFS Traversal: The depth-first search (DFS) traversal visits each node exactly once in both trees. so, the time complexity for traversing both trees is
, where nis the number of nodes in the first tree andmis the number of nodes in the second tree. - Comparing Leaf Sequences: The comparison of two leaf sequences (lists) has a complexity of
, where kis the number of leaf nodes in the smaller list. In the worst case,kcould be as large asmin(n, m).
Thus, the overall time complexity of the algorithm is k is bounded by n and m.
Space Complexity
- Space for Leaf Sequences: The space required to store the leaf sequences of both trees is proportional to the number of leaf nodes. In the worst case, a binary tree can have up to
n/2leaves (for a perfectly balanced tree), so the space complexity for the leaf lists is, which simplifies to . - Recursive Stack Space: The DFS traversal incurs additional space cost due to recursive function calls, which in the worst case (a skewed tree) could be
, where h1andh2are the heights of the two trees.
The overall space complexity, considering both the space for leaf sequences and the recursive stack space, is h1 + h2 is much smaller than the number of nodes, leading to an overall space complexity closer to
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity